class Solution {
public:
    string longestPalindrome(string s)
    {
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n));
        string aus;
        for(int l=0;l<n;l++)
        {
            for(int i=0;i+l<n;i++)
            {
                int j=i+l;
                if(l==0) dp[i][j]=1;
                if(l==1) dp[i][j]=(s[i]==s[j])?1:0;
                else     dp[i][j]=(s[i]==s[j] && dp[i+1][j-1])?1:0;

                if(dp[i][j] && aus.size()<l+1)
                    aus=s.substr(i,l+1);
            }
        }
        return aus;
    }
};
